package graph

import (
	llq "github.com/emirpasic/gods/queues/linkedlistqueue"
)

// graph is 1-based.
func hasCycle(graph [][]int, numPoints int) bool {
	onPath, visited := make([]bool, numPoints+1), make([]bool, numPoints+1)
	has := false

	var traverse func(graph [][]int, start int)
	traverse = func(graph [][]int, start int) {
		if onPath[start] {
			has = true
		}

		if visited[start] || has {
			return
		}

		visited[start] = true
		onPath[start] = true

		for _, p := range graph[start] {
			traverse(graph, p)
		}

		onPath[start] = false
	}

	for i := 1; i <= numPoints; i++ {
		traverse(graph, i)
	}

	return has
}

func topologicalSorting(graph [][]int, n int) []int {
	que := llq.New()
	inDegrees := make([]int, n+1)
	ret := make([]int, 0, n)
	for i := 0; i < n; i++ {
		for _, nxt := range graph[i] {
			inDegrees[nxt]++
		}
	}

	for idx := 1; idx <= n; idx++ {
		if inDegrees[idx] == 0 {
			que.Enqueue(idx)
		}
	}

	for !que.Empty() {
		cur, _ := que.Dequeue()
		curIdx := cur.(int)
		ret = append(ret, curIdx)
		for _, nxt := range graph[curIdx] {
			inDegrees[nxt]--
			if inDegrees[nxt] == 0 {
				que.Enqueue(nxt)
			}
		}
	}

	return ret
}
